#ifndef LOCK_FREE_RING_QUEUE_H
#define LOCK_FREE_RING_QUEUE_H

#include <atomic>
#include <memory>
#include <stdexcept>
#include <thread>

template <typename T>
class LockFreeRingQueue {
 public:
  // Constructor that initializes the ring queue with the specified size
  explicit LockFreeRingQueue(uint32_t size);

  // Default destructor
  ~LockFreeRingQueue() = default;

  // Disable copy constructor and assignment operator
  LockFreeRingQueue(const LockFreeRingQueue&) = delete;
  LockFreeRingQueue& operator=(const LockFreeRingQueue&) = delete;

  // Enqueue operation to add an element to the queue
  bool Enqueue(const T& data);

  // Dequeue operation to remove an element from the queue
  bool Dequeue(T* data);

  // Check if the queue is empty
  bool IsEmpty() const noexcept;

  // Check if the queue is full
  bool IsFull() const noexcept;

  // Get the current size of the queue
  uint32_t Size() const noexcept;

 private:
  // Check if the given number is a power of two
  static bool IsPowerOfTwo(uint32_t num) noexcept;

  // Calculate the ceiling power of two greater than or equal to the given number
  static uint32_t CeilPowerOfTwo(uint32_t num) noexcept;

  // Round up the given number to the nearest power of two
  static uint32_t RoundupPowerOfTwo(uint32_t num) noexcept;

  // Get the index within the queue
  uint32_t IndexOfQueue(uint32_t index) const noexcept;

 private:
  const uint32_t size_;                     // Size of the queue, must be a power of two
  std::atomic<uint32_t> length_;            // Current length of the queue
  std::atomic<uint32_t> read_index_;        // Index for the consumer to read
  std::atomic<uint32_t> write_index_;       // Index for the producer to write
  std::atomic<uint32_t> last_write_index_;  // Last confirmed write index
  std::unique_ptr<T[]> queue_;              // Array to store the queue elements
};

template <typename T>
LockFreeRingQueue<T>::LockFreeRingQueue(uint32_t size)
    : size_(size <= 1U           ? 2U
            : IsPowerOfTwo(size) ? size
                                 : RoundupPowerOfTwo(size)),
      length_(0U),
      read_index_(0U),
      write_index_(0U),
      last_write_index_(0U),
      queue_(std::make_unique<T[]>(size_)) {
  if (size == 0U) {
    throw std::out_of_range("Queue size must be greater than 0");
  }
}

template <typename T>
bool LockFreeRingQueue<T>::Enqueue(const T& data) {
  uint32_t current_read_index;
  uint32_t current_write_index;

  do {
    current_read_index = read_index_.load(std::memory_order_relaxed);
    current_write_index = write_index_.load(std::memory_order_relaxed);

    // Check if the queue is full
    if (IndexOfQueue(current_write_index + 1U) == IndexOfQueue(current_read_index)) {
      return false;  // Queue is full
    }
  } while (!write_index_.compare_exchange_weak(current_write_index, current_write_index + 1U, std::memory_order_release,
                                               std::memory_order_relaxed));

  queue_[IndexOfQueue(current_write_index)] = data;

  // Confirm the write operation
  while (!last_write_index_.compare_exchange_weak(current_write_index, current_write_index + 1U,
                                                  std::memory_order_release, std::memory_order_relaxed)) {
    std::this_thread::yield();  // Yield CPU to avoid busy-waiting
  }

  length_.fetch_add(1U, std::memory_order_relaxed);

  return true;
}

template <typename T>
bool LockFreeRingQueue<T>::Dequeue(T* data) {
  if (data == nullptr) {
    throw std::invalid_argument("Null pointer passed to Dequeue");
  }

  uint32_t current_read_index;
  uint32_t current_last_write_index;

  do {
    current_read_index = read_index_.load(std::memory_order_relaxed);
    current_last_write_index = last_write_index_.load(std::memory_order_relaxed);

    // Check if the queue is empty
    if (IndexOfQueue(current_last_write_index) == IndexOfQueue(current_read_index)) {
      return false;  // Queue is empty
    }

    *data = queue_[IndexOfQueue(current_read_index)];

    if (read_index_.compare_exchange_weak(current_read_index, current_read_index + 1U, std::memory_order_release,
                                          std::memory_order_relaxed)) {
      length_.fetch_sub(1U, std::memory_order_relaxed);
      return true;
    }
  } while (true);
}

template <typename T>
bool LockFreeRingQueue<T>::IsEmpty() const noexcept {
  return length_.load(std::memory_order_relaxed) == 0U;
}

template <typename T>
bool LockFreeRingQueue<T>::IsFull() const noexcept {
  uint32_t next_write_index = IndexOfQueue(write_index_.load(std::memory_order_relaxed) + 1U);
  return next_write_index == read_index_.load(std::memory_order_acquire);
}

template <typename T>
uint32_t LockFreeRingQueue<T>::Size() const noexcept {
  return length_.load(std::memory_order_relaxed);
}

template <typename T>
bool LockFreeRingQueue<T>::IsPowerOfTwo(uint32_t num) noexcept {
  return (num != 0U) && ((num & (num - 1U)) == 0U);
}

template <typename T>
uint32_t LockFreeRingQueue<T>::CeilPowerOfTwo(uint32_t num) noexcept {
  num |= (num >> 1U);
  num |= (num >> 2U);
  num |= (num >> 4U);
  num |= (num >> 8U);
  num |= (num >> 16U);
  return num - (num >> 1U);
}

template <typename T>
uint32_t LockFreeRingQueue<T>::RoundupPowerOfTwo(uint32_t num) noexcept {
  return CeilPowerOfTwo((num - 1U) << 1U);
}

template <typename T>
uint32_t LockFreeRingQueue<T>::IndexOfQueue(uint32_t index) const noexcept {
  return index & (size_ - 1U);
}

#endif  // LOCK_FREE_RING_QUEUE_H
